﻿namespace Leetcode.N0207;
public class Solution
{
    public bool CanFinish(int numCourses, int[][] prerequisites)
    {
        var edges = new Dictionary<int, IList<int>>(prerequisites.Length);
        var inDeg = new int[numCourses];
        for (var i = 0; i < prerequisites.Length; i++)
        {
            var item = prerequisites[i];
            if (!edges.ContainsKey(item[0]))
            {
                edges.Add(item[0], new List<int>());
            }
            edges[item[0]].Add(item[1]);
            inDeg[item[1]]++;
        }

        var queue = new Queue<int>();

        var visited = 0;
        for (int i = 0; i < inDeg.Length; i++)
        {
            if (inDeg[i] == 0)
            {
                queue.Enqueue(i);
                visited++;
            }
        }

        while (queue.Count > 0)
        {
            var outItem = queue.Dequeue();
            if (!edges.ContainsKey(outItem))
            {
                continue;
            }

            foreach (var inItem in edges[outItem])
            {
                inDeg[inItem]--;
                if (inDeg[inItem] == 0)
                {
                    visited++;
                    queue.Enqueue(inItem);
                }
            }
        }

        return visited == numCourses;
    }
}